%%%-------------------------------------------------------------------
%%% @author Plamen Dragozov <plamen@dragozov.com>
%%% @copyright (C) 2010, Plamen Dragozov
%%% @doc
%%% EUnit tests for the treap module.
%%% @end
%%% Created : 22 Jul 2010
%%%-------------------------------------------------------------------
-module(treap_test).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").

%%--------------------------------------------------------------------
%% Unit test functions for the methods in the treap module
%%--------------------------------------------------------------------
new_test()->
    ?assert(treap:new() =:= empty).

append_test() ->
    %test appending a value into an empty treap
    {_, k1, [v11], empty, empty} = treap:append(k1, v11, treap:new()),
    %test appending 2 values at the same key
    {_, k1, Values, empty, empty} = treap:append(k1, v12, treap:append(k1, v11, treap:new())),
    ?assert(lists:member(v11, Values) andalso lists:member(v12, Values)),
    
    %Insert 100 random key/values in both a dictionary and a treap
    {T, D} = lists:foldl(fun(_, {AccT, AccD}) -> 
				 K = random:uniform(1000),
				 V = random:uniform(1000),
				 NewAccT = treap:append(K, V, AccT),
				 NewAccD = dict:append(K, V, AccD),
				 {NewAccT, NewAccD}
			 end, 
			 {treap:new(), dict:new()}, 
			 lists:seq(1, 100)),
    %for all keys in D check if they are in T and their values match
    ?assert(validate_treap_with_dict_find(T, D)),
    %Validate the nodes' priority and key order
    ?assert(validate_treap(T, empty, top)).

append_list_test() ->
    %append_list with a non_list value is the same as append
    {_, k1, [v11], empty, empty} = treap:append_list(k1, v11, treap:new()),
    %append_list with a list for a missing key adds uses the list as a value
    {_, k1, [v11], empty, empty} = treap:append_list(k1, [v11], treap:new()),
    {_, k1, [v11, v12, v13], empty, empty} = treap:append_list(k1, [v11, v12, v13], treap:new()),
    %append_list with the same key
    {_, k1, Values, empty, empty} = treap:append_list(k1, v12, treap:append_list(k1, v11, treap:new())),
    ?assert(lists:member(v11, Values) andalso lists:member(v12, Values)),
    {_, k1, Values1, empty, empty} = treap:append_list(k1, v14, treap:append_list(k1, [v11, v12, v13], treap:new())),
    VList = [v11, v12, v13, v14],
    ?assert(length(Values1) =:= length(VList) andalso (VList -- Values1 =:= [])),
    {_, k1, Values2, empty, empty} = treap:append_list(k1, [v13, v14], treap:append_list(k1, [v11, v12], treap:new())),
    ?assert(length(Values2) =:= length(VList) andalso (VList -- Values2 =:= [])),
    %Insert 100 random key/values in both a dictionary and a treap using append_list
    {T, D} = lists:foldl(fun(_, {AccT, AccD}) -> 
				 K = random:uniform(1000),
				 Start = random:uniform(1000),
				 End = Start + random:uniform(10),
				 V = lists:seq(Start, End),
				 NewAccT = treap:append_list(K, V, AccT),
				 NewAccD = dict:append_list(K, V, AccD),
				 {NewAccT, NewAccD}
			 end, 
			 {treap:new(), dict:new()}, 
			 lists:seq(1, 100)),
    %for all keys in D check if they are in T and their values match
    ?assert(validate_treap_with_dict_find(T, D)),
    %Validate the nodes' priority and key order
    ?assert(validate_treap(T, empty, top)).

erase_test() ->
    empty = treap:erase(k1, treap:append_list(k1, v11, treap:new())),
    {_, k2, [v21], empty, empty} = treap:erase(k1, treap:append_list(k2, v21, treap:append_list(k1, v11, treap:new()))),
    {T, D} = treap_dict_with_erase(1000),
    %for all keys in D check if they are in T and their values match
    ?assert(validate_treap_with_dict_find(T, D)),
    %Validate the nodes' priority and key order of the treap
    ?assert(validate_treap(T, empty, top)).


store_test() ->
    %storing a new key behaves as append
    {_, k1, [v11], empty, empty} = treap:store(k1, v11, treap:new()),
    {_, k1, [v11, v12], empty, empty} = treap:store(k1, [v11, v12], treap:new()),
    %store replaces an old value
    {_, k1, [v12], empty, empty} = treap:store(k1, v12, treap:store(k1, v11, treap:new())),
    {_, k1, [v12, v13], empty, empty} = treap:store(k1, [v12, v13], treap:store(k1, v11, treap:new())),
    %Insert 100 random key/values in both a dictionary and a treap
    {T, D} = lists:foldl(fun(_, {AccT, AccD}) -> 
				 K = random:uniform(1000),
				 V = random:uniform(1000),
				 NewAccT = treap:store(K, V, AccT),
				 NewAccD = dict:store(K, V, AccD),
				 {NewAccT, NewAccD}
			 end, 
			 {treap:new(), dict:new()}, 
			 lists:seq(1, 100)),
    %for all keys in D check if they are in T and their values match
    ?assert(validate_treap_with_dict_find(T, D)),
    %Validate the nodes' priority and key order
    ?assert(validate_treap(T, empty, top)).


fetch_find_test() ->
    {ok, [v11]} = treap:find(k1, treap:store(k1, v11, treap:new())),
    [v11] = treap:fetch(k1, treap:store(k1, v11, treap:new())),
    error = treap:find(k2, treap:store(k1, v11, treap:new())),
    error = treap:find(k, treap:new()),
    ?assertError({not_found, k2}, treap:fetch(k2, treap:store(k1, v11, treap:new()))),
    ?assertError({not_found, k}, treap:fetch(k, treap:new())),
    {T, D} = treap_dict_with_erase(1000),
    ?assert(validate_treap_with_dict_find(T, D)),
    ?assert(validate_treap_with_dict_fetch(T, D)).

fetch_keys_test() ->
    [k1] = treap:fetch_keys(treap:store(k1, v11, treap:new())),
    [] = [k1, k2, k3] -- treap:fetch_keys(treap:store(k3, v31, treap:store(k2, v21, treap:store(k1, v11, treap:new())))),
    {T, D} = treap_dict_with_erase(1000),
    KeysT = treap:fetch_keys(T),
    KeysD = dict:fetch_keys(D),
    ?assert((length(KeysT) =:= length(KeysD)) andalso (KeysD -- KeysT =:= [])).

fetch_keyslr_test() ->
    [k1] = treap:fetch_keysl(treap:store(k1, v11, treap:new())),
    [k1] = treap:fetch_keysr(treap:store(k1, v11, treap:new())),
    [1, 2, 7] = treap:fetch_keysl(treap:store(2, v2, treap:store(7, v7, treap:store(1, v1, treap:new())))),
    [7, 2, 1] = treap:fetch_keysr(treap:store(2, v2, treap:store(7, v7, treap:store(1, v1, treap:new())))),
    {T, D} = treap_dict_with_erase(1000),
    KeysTL = treap:fetch_keysl(T),
    KeysTR = treap:fetch_keysr(T),
    KeysD = dict:fetch_keys(D),
    L = length(KeysD),
    ?assert((length(KeysTL) =:= L) andalso (length(KeysTR) =:= L)),
    KeysTL = lists:sort(KeysD),
    KeysTR = lists:reverse(KeysTL).

split_test() ->
    N = 1000,
    T = treap_from_list(lists:seq(1, N)),
    {empty, T} = treap:split(0, T),
    {T, empty} = treap:split(N + 1, T),
    {TL, TR} = treap:split(N div 2, T),
    {KTL, KTR} = {treap:fetch_keysl(TL), treap:fetch_keysl(TR)},
    KTL = lists:seq(1, N div 2),
    KTR = lists:seq(N div 2 + 1, N),
    T1 = treap_with_erase(N),
    Split = (N div 10) + random:uniform(N div 2),
    {T1L, T1R} = treap:split(Split, T1),
    ?assert(validate_treap(T1L) andalso validate_treap(T1R)),
    ?assert(treap:fold(fun(K, _, Acc) ->
		       Acc andalso K =< Split
	       end,
	       true,
	       T1L)),
    ?assert(treap:fold(fun(K, _, Acc) ->
		       Acc andalso K >= Split
	       end,
	       true,
	       T1R)).

unsplit_test() ->
    N = 1000,
    T1 = treap_from_list(lists:seq(1, N div 2)),
    T2 = treap_from_list(lists:seq(N div 2 + 1, N)),
    T12 = treap:unsplit(T1, T2),
    ?assert(treap:fetch_keysl(T12) =:= lists:seq(1, N)),
    T = treap_with_erase(N),
    {TL, TR} = treap:split(N div 2, T),
    TU = treap:unsplit(TL, TR),
    ?assert(validate_treap(TU)),
    Keys = treap:fetch_keysl(TU),
    KeysL = treap:fetch_keysl(TL),
    KeysR = treap:fetch_keysl(TR),
    Keys = KeysL ++ KeysR,
    Keys = treap:fetch_keysl(T).
    
filter_test() ->
    N = 1000,
    T1 = treap_from_list(lists:seq(1, N)),
    empty = treap:filter(fun(_, _) ->
				 false
			 end, 
			 T1),
    T1 = treap:filter(fun(_, _) ->
			      true
		      end, 
		      T1),
    {T, D} = treap_dict_with_erase(N),
    R = random:uniform(4) + 1, %2 - 5
    Fun = fun(K,_) ->
		  K rem R =:= 0
	  end,
    NewT = treap:filter(Fun,T),
    NewD = dict:filter(Fun, D),
    ?assert(validate_treap(NewT)),
    ?assert(validate_treap_with_dict_find(NewT, NewD)).

is_key_test() ->
    N = 1000,
    ?assert(treap:is_key(k1, treap:store(k1, v1, treap:new()))),
    ?assertNot(treap:is_key(k1, treap:new())),
    ?assertNot(treap:is_key(k2, treap:store(k1, v1, treap:new()))),
    {T, D} = treap_dict_with_erase(N),
    
    ?assertNot(treap:is_key(-random:uniform(N), T)),
    ?assertNot(treap:is_key(N + random:uniform(N), T)),
    Keys = dict:fetch_keys(D),
    Missing = lists:seq(1, N) -- Keys,
    ?assertNot(lists:foldl(fun(X, Acc) ->
				   Acc orelse treap:is_key(X, T)
			   end,
			   false,
			   Missing)),
    ?assert(lists:foldl(fun(X, Acc) ->
				Acc andalso treap:is_key(X, T)
			end,
			true,
			Keys)).

map_test() ->
    
    {_, _, [test], empty, empty} = treap:map(fun(_, _) ->
						     test
					    end,
					    treap:store(1, 2, treap:new())),
    {_, _, [test1], empty, empty} = treap:map(fun(_, _) ->
						     [test1]
					    end,
					    treap:store(1, 2, treap:new())),
    {_, _, [test1, test2], empty, empty} = treap:map(fun(_, _) ->
						     [test1, test2]
					    end,
					    treap:store(1, 2, treap:new())),
    empty = treap:map(fun(_, _) ->
			      test
		      end, empty),
    
    {T, D} = treap_dict_with_erase(1000),
    R = random:uniform(10),
    Fun = fun(K, L) ->
		   lists:foldl(fun(X, Acc) ->
				       [(K div R) * X | Acc]
			       end,
			       [],
			       L)
	   end,
    D1 = dict:map(Fun, D),
    T1 = treap:map(Fun, T),
    ?assert(validate_treap(T)),
    ?assert(validate_treap_with_dict_find(T1, D1)).

merge_test() ->
    empty = treap:merge(fun(_, _, _) ->
				any
			end, 
			empty,
			empty),
    T = treap_from_list(lists:seq(1, 100)),
    T = treap:merge(fun(_, _, _) ->
				any
			end, 
			T,
			empty),
    T = treap:merge(fun(_, _, _) ->
				any
			end, 
			empty,
			T),
    {T1, D1} = treap_dict_with_erase(1000),
    {T2, D2} = treap_dict_with_erase(1000),
    Fun = fun(_, V1, V2) ->
		  V1 ++ (V2 -- V1)
	  end,
    DM = dict:merge(Fun, D1, D2),
    TM = treap:merge(Fun, T1, T2),
    ?assert(validate_treap(TM)),
    ?assert(validate_treap_with_dict_find(TM, DM)).

to_list_test() ->
    [] = treap:to_list(empty),
    [] = treap:to_listl(empty),
    [] = treap:to_listr(empty),
    Tr = treap:store(k, v, treap:new()),
    [{k, [v]}] = treap:to_list(Tr),
    [{k, [v]}] = treap:to_listl(Tr),
    [{k, [v]}] = treap:to_listr(Tr),
    {T, D} = treap_dict_with_erase(1000),
    LT = treap:to_list(T),
    LTL = treap:to_listl(T),
    LTR = treap:to_listr(T),
    Len = dict:size(D),
    ?assert(length(LT) =:= Len andalso length(LTL) =:= Len andalso length(LTR) =:= Len),
    
    Fun = fun({K, V}, Acc) -> 
		  VD = dict:fetch(K, D), 
		  Acc andalso (length(V) =:= length(VD)) andalso (VD -- V =:= [])
		end,
    ?assert(lists:foldl(Fun, true, LT)),
    ?assert(lists:foldl(Fun, true, LTL)),
    ?assert(lists:foldl(Fun,true, LTR)).

from_list_test() ->
    empty = treap:from_list([]),
    {_, k, [v], empty, empty} = treap:from_list([{k, v}]),
    {_, k, [v1, v2], empty, empty} = treap:from_list([{k, [v1, v2]}]),
    {_, k, V, empty, empty} = treap:from_list([{k, v1}, {k, v2}]),
    ?assert(lists:member(v1, V) andalso lists:member(v2, V)),
    N = 1000,
    L = [{random:uniform(N), random:uniform(N)} || _ <- lists:seq(1, N)],
    T = treap:from_list(L),
    ?assert(validate_treap(T)),
    ?assert(lists:foldl(fun({K, [_|_] = Val}, Acc) -> 
				ValT = treap:fetch(K, T),
				Acc andalso (length(Val) =:= length(ValT)) andalso (Val -- ValT =:= []);
			   ({K, Val}, Acc) ->
				Acc andalso lists:member(Val, treap:fetch(K, T))
			end, 
			true,
			L)).

foreach_test() ->
    Tbl = ets:new(foreach_test, [duplicate_bag, public]), 
    Fun = fun(K, V) ->
			  ets:insert(Tbl, {items, {K,V}})
		  end,
    treap:foreach(Fun, empty),
    0 = ets:info(Tbl, size),
    treap:foreachl(Fun, empty),
    0 = ets:info(Tbl, size),
    treap:foreachr(Fun, empty),
    0 = ets:info(Tbl, size),
    treap:foreach_spawn(Fun, empty),
    0 = ets:info(Tbl, size),
    
    T = treap_with_erase(1000),
    LT = treap:to_list(T),

    treap:foreach(Fun, T),
    L = [KV || {_, KV} <- ets:lookup(Tbl, items)],    
    ?assert(length(LT) =:= length(L) andalso L -- LT =:= []),
    ets:delete(Tbl, items),

    treap:foreachl(Fun, T),
    LL = [KV || {_, KV} <- ets:lookup(Tbl, items)],    
    ?assert(length(LT) =:= length(LL) andalso LL -- LT =:= []),
    ets:delete(Tbl, items),

    treap:foreachl(Fun, T),
    LR = [KV || {_, KV} <- ets:lookup(Tbl, items)],    
    ?assert(length(LT) =:= length(LR) andalso LR -- LT =:= []),
    ets:delete(Tbl, items),

    Fun1 = fun(K, _) ->
		  ets:insert(Tbl, {keys, K})
	  end,
    treap:foreachl(Fun1, T),
    KeysTL = treap:fetch_keysl(T),
    KeysTblL = [KV || {_, KV} <- ets:lookup(Tbl, keys)],
    ?assert(KeysTblL =:= KeysTL),
    ets:delete(Tbl, keys),
    
    treap:foreachr(Fun1, T),
    KeysTR = treap:fetch_keysr(T),
    KeysTblR = [KV || {_, KV} <- ets:lookup(Tbl, keys)],
    ?assert(KeysTblR =:= KeysTR),
    ets:delete(Tbl, keys),
    Self = self(),
    Fun2 = fun(K, V) ->
		   Self ! {self(), {K, V}}
	  end,
    TSize = length(KeysTL),
    RFun = fun(Count, _) when Count =:= TSize->
		   Count;
	      (Count, SelfFun)->
		   receive
		       {From, KV} ->
			   ets:insert(Tbl, {items, KV}),
			   ets:insert(Tbl, {pids, From}),
			   SelfFun(Count + 1, SelfFun)
		   after 
		       5000 ->
			   erlang:error(timeout)
		   end
	   end,
    treap:foreach_spawn(Fun2, T),
    RFun(0, RFun),
    Items = [KV || {_, KV} <- ets:lookup(Tbl, items)],    
    ?assert(length(LT) =:= length(Items) andalso Items -- LT =:= []),
    Pids = [Pid || {_, Pid} <- ets:lookup(Tbl, pids)],
    ?assert(length(Pids) =:= length(Items)),
    ets:delete(Tbl).

fold_test() ->
    IncFun = fun(_, _, I) -> I + 1 end,
    0 = treap:fold(IncFun, 0, empty),
    0 = treap:foldl(IncFun, 0, empty),
    0 = treap:foldr(IncFun, 0, empty),
    1 = treap:fold(IncFun, 0, treap:store(k, v, treap:new())),
    1 = treap:foldl(IncFun, 0, treap:store(k, v, treap:new())),
    1 = treap:foldr(IncFun, 0, treap:store(k, v, treap:new())),

    ItemFun = fun(K, V, Acc) ->
		      [{K, V} | Acc]
	      end,
    [{3,[v3]}, {2,[v2]}, {1,[v1]}] = treap:foldl(ItemFun, [], treap:store(2, v2, treap:store(1, v1, treap:store(3, v3, treap:new())))),
    [{1,[v1]}, {2,[v2]}, {3,[v3]}] = treap:foldr(ItemFun, [], treap:store(2, v2, treap:store(1, v1, treap:store(3, v3, treap:new())))),

    {T, D} = treap_dict_with_erase(1000),
    Items = treap:fold(ItemFun, [], T),
    ItemsL = treap:foldl(ItemFun, [], T),
    ItemsR = treap:foldr(ItemFun, [], T),
    ItemsD = dict:to_list(D),
    Len = length(ItemsD),
    ?assert(Len =:= length(Items) andalso Len =:= length(ItemsL) andalso Len =:= length(ItemsR)),
    lists:foldl(fun({K, V}, Acc) -> 
			Vals = dict:fetch(K, D),
			Acc andalso (length(Vals) =:= length(V)) andalso (Vals -- V =:= [])
		end, 
		true, 
		Items),
    ItemsR = lists:sort(Items),
    ItemsL = lists:reverse(ItemsR).

to_dict_test() ->
    EmptyD = treap:to_dict(empty),
    0 = dict:size(EmptyD),
    EmptyD = treap:to_dict(empty, EmptyD),
    T = treap_with_erase(1000),
    D = treap:to_dict(T),
    ?assert(validate_treap_with_dict_find(T, D)),
    M = 500,
    L1 = [{K, [random:uniform(1000)]} || K <- lists:seq(1, M)],
    D1 = dict:from_list(L1),
    L2 = [{K, [random:uniform(1000)]} || K <- lists:seq(M + 1, 2*M)],
    T1 = treap:from_list(L2),
    D2 = treap:to_dict(T1, D1),
    L3 = dict:to_list(D2),
    L4 = L1 ++ L2,
    ?assert(length(L3) =:= length(L4) andalso L4 -- L3 =:= []).

from_dict_test() ->
    empty = treap:from_dict(dict:new()),
    {_, k, [v], empty, empty} = treap:from_dict(dict:new(), treap:store(k, v, treap:new())),
    N = 1000,
    L = [{random:uniform(N), [random:uniform(N)]} || _ <- lists:seq(1, N)], 
    D = dict:from_list(L),
    T = treap:from_dict(D),
    ?assert(validate_treap_with_dict_find(T, D)),
    M = 500,
    L1 = [{K, [random:uniform(N)]} || K <- lists:seq(1, M)],
    T1 = treap:from_list(L1),
    L2 = [{K, [random:uniform(N)]} || K <- lists:seq(M + 1, 2*M)],
    D1 = dict:from_list(L2),
    T2 = treap:from_dict(D1, T1),
    L3 = treap:to_list(T2),
    L4 = L1 ++ L2,
    ?assert(length(L3) =:= length(L4) andalso L4 -- L3 =:= []).

size_test() ->
    0 = treap:size(empty),
    1 = treap:size(treap:store(k, v, treap:new())),
    {T, D} = treap_dict_with_erase(1000),
    ?assert(dict:size(D) =:= treap:size(T)).
    
count_values_test() ->
    0 = treap:count_values(empty),
    1 = treap:count_values(treap:store(k, v, treap:new())),
    3 = treap:count_values(treap:append(k1, v12, treap:append(k2, v21, treap:append(k1, v11, treap:new())))),
    {T, D} = treap_dict_with_erase(1000),
    ?assert(dict:fold(fun(_, V, Acc) -> Acc + length(V) end, 0, D) =:= treap:count_values(T)).

update3_test() ->
    ?assertError({not_found, missing_key}, treap:update(missing_key, fun(V) -> V end,empty)),
    {_, k, [-1],empty, empty} = treap:update(k, fun([V]) -> -V end, treap:store(k, 1, treap:new())),
    ?assertError({not_found, k}, treap:update(k, fun([V]) -> -V end, treap:store(k1, 1, treap:new()))),
    {T, D} = treap_dict_with_erase(1000),
    Fun = fun(V) -> [-X || X <- V] end,
    Keys = treap:fetch_keysl(T),
    {NewT, NewD} = lists:foldl(fun(K, {Tr, Di}) -> {treap:update(K, Fun, Tr), dict:update(K, Fun, Di)} end, {T, D}, Keys),
    ?assert(validate_treap(NewT)),
    ?assert(validate_treap_with_dict_find(NewT, NewD)),
    ?assert(treap:fold(fun(_, V, Acc) ->
			    Acc andalso lists:foldl(fun(X, Acc1) -> Acc1 andalso X =< 0 end, true, V)
		       end,
		       true,
		       NewT)).

update4_test() ->
    {_, k, [v], empty, empty} = treap:update(k, fun(V) -> V end, v, empty),
    {_, k, [-1], empty, empty} = treap:update(k, fun([V]) -> -V end, v, treap:store(k, 1, treap:new())),
    N = 1000,
    {T, D} = treap_dict_with_erase(N),
    {NewT, NewD} = lists:foldl(fun(_, {Tr, Di}) -> 
				       NewV = random:uniform(N),
				       Initial = random:uniform(N),
				       K = random:uniform(N),
				       Fun = fun(_) ->
						  [NewV]
					     end,	 
				       {treap:update(K, Fun, Initial, Tr), dict:update(K, Fun, Initial, Di)} end, {T, D}, lists:seq(1, N)),
    ?assert(validate_treap(NewT)),
    ?assert(validate_treap_with_dict_find(NewT, NewD)).

update_counter_test() ->
    {_, k, [3], empty, empty} = treap:update_counter(k, 3, empty),
    {_, k, [8], empty, empty} = treap:update_counter(k, 5, treap:update_counter(k, 3, empty)),
    N = 1000,
    {T, D} = lists:foldl(fun(_, {T, D}) ->
				 K = random:uniform(N),
				 Inc = random:uniform(N),
				 {treap:update_counter(K, Inc, T), dict:update_counter(K, Inc, D)}
			 end,
			 {treap:new(), dict:new()},
			 lists:seq(1, N)),
    ?assert(validate_treap_with_dict_find(T, D)).

%%---------------
%%Private methods
%%---------------
validate_treap(T) ->
    validate_treap(T, empty, top).
validate_treap({_, _, _, B, A} = Node, empty, _) ->
		       validate_treap(B, Node, left) andalso validate_treap(A, Node, right);
validate_treap({P, K, _, B, A} = Node, {ParentP, ParentK, _, _, _}, left) when (P =< ParentP) andalso (K < ParentK) ->
		       validate_treap(B, Node, left) andalso validate_treap(A, Node, right);
validate_treap({P, K, _, B, A} = Node, {ParentP, ParentK, _, _, _}, right) when (P =< ParentP) andalso (K > ParentK) -> 
		       validate_treap(B, Node, left) andalso validate_treap(A, Node, right);
validate_treap(empty, _, _) ->
		       true;
validate_treap({_P1, _K1, _, _, _}, {_P2, _K2, _, _, _}, _Pos) ->
		       false.

validate_treap_with_dict_fetch(T, D) ->
    dict:fold(fun(K, V, Acc) ->
			      Acc andalso case V of
					      _ when is_list(V) ->
						  V1 = treap:fetch(K, T),
						  length(V) =:= length(V1) andalso V -- V1 =:= [];
					      _ ->
						  [V] =:= treap:fetch(K, T)
					  end
		      end, 
		      true, 
		      D).

validate_treap_with_dict_find(T, D) ->
    dict:fold(fun(K, V, Acc) ->
			      Acc andalso case V of
					       _ when is_list(V) ->
						  {ok, V1} = treap:find(K, T),
						  length(V) =:= length(V1) andalso V -- V1 =:= [];
					      _ ->
						  {ok, [V]} =:= treap:find(K, T)
					  end
		      end, 
		      true, 
		      D).

treap_from_list(L) ->
    lists:foldl(fun(X, Acc) ->
			treap:append(X, {values, X}, Acc)
		end,
		treap:new(),
		L).
				     

%%These methods
treap_dict_with_erase(Size) ->
    %Insert Size random key/values in both a dictionary and a treap and randomly delete some (but the same) keys from both
    lists:foldl(fun(_, {AccT, AccD}) -> 
			K = random:uniform(Size),
			V = random:uniform(Size),
			TmpAccT = treap:append(K, V, AccT),
			TmpAccD = dict:append(K, V, AccD),
			%Randomly delete some of the existing keys
			case random:uniform(20) of % Chance of 5%
			    1 ->
				Keys = dict:fetch_keys(TmpAccD),
				lists:foldl(fun(X, {AccT1, AccD1}) -> case random:uniform(100) of
									  1 ->
									      {treap:erase(X, AccT1), dict:erase(X, AccD1)};
									  _ -> 
									      {AccT1, AccD1}
								      end
					    end,
					    {TmpAccT, TmpAccD},
					    Keys);
			    _ -> {TmpAccT, TmpAccD}
			end
		end,
		{treap:new(), dict:new()}, 
		lists:seq(1, Size)).

treap_with_erase(Size) ->
    %Insert Size random key/values in a treap and randomly delete some
    lists:foldl(fun(_, Acc) -> 
			K = random:uniform(Size),
			V = random:uniform(Size),
			TmpAcc = treap:append(K, V, Acc),
			%Randomly delete some of the existing keys
			case random:uniform(20) of % Chance of 5%
			    1 ->
				Keys = treap:fetch_keys(TmpAcc),
				lists:foldl(fun(X, Acc1) -> case random:uniform(100) of 
								1 ->
								    treap:erase(X, Acc1);
								_ -> 
								    Acc1
							    end
					    end,
					    TmpAcc,
					    Keys);
			    _ -> TmpAcc
			end
		end,
		treap:new(), 
		lists:seq(1, Size)).
